#include "unordered.h"
#include <float.h>

UnorderedArray::UnorderedArray()
	:  tail(0)
{
	// Malloc instead of new, in case you ever want to add extra elements
	// beyond the initial size of the array
	//edgeArray = (Edge*)malloc(sizeof(Edge) * size);
	//for (int i = 0; i < size; i++)
	//	edgeArray[i] = Edge();
}

void UnorderedArray::insert(Edge edge)
{
	// Since malloc was used instead of new, realloc can be used to create
	// larger arrays if needed
	/*if (tail >= size)
	{
#if DEBUG
		std::cerr << "Reallocing unordered array\n";
#endif
		int oldSize = size;
		size *= 2;
		edgeArray = (Edge*)realloc(edgeArray, sizeof(Edge) * size);
		for (int i = oldSize; i < size; i++)
			edgeArray[i] = Edge();
	}
	
	edgeArray[tail++] = edge;
	*/
	//fprintf(stderr, "INSERT() tail: %d\n", tail);
	
	if (tail >= (int) edgeVector.size())
		edgeVector.push_back(edge);
	else
		edgeVector[tail] = edge;
		
		
	tail++;
	
}

Edge UnorderedArray::deleteMin()
{
	float minCost = FLT_MAX;
	int minPos = -1;

	for (int i = 0; i < tail; i++)
		if (edgeVector[i].cost < minCost)
		{
			minPos = i;
			minCost = edgeVector[i].cost;
		}

	if (minPos == -1)
		throw std::runtime_error("Unable to delete minimum edge from array");

	// Other possibilities are an array of flags to check whether an element
	// has already been removed or not, but that uses extra memory, you could
	// also free memory when enough elements are removed
	std::swap(edgeVector[minPos], edgeVector[tail - 1]);

	return edgeVector[--tail];
}
